package com.dlut.java;

import java.util.Arrays;

public class RobotAndClothes {

    // 解题思路:
    // 二分答案
    // 定义函数minPower：
    // 如果一定要在time时间内捡完所有衣服，请返回使用最少的电量
    // 如果minPower，这个函数能实现
    // 那么只要二分出最小的答案即可
    public static int fast(int n, int b, int[] powers, int[] rates) {
        if (n == 0) {
            return 0;
        }
        if (b == 0 || powers[0] > b) {
            return -1;
        }
        // 最小时间只可能在[1, rates[0] * n]范围上
        int l = 1;
        int r = rates[0] * n;
        int m = 0;
        int ans = -1;
        // 二分答案
        // 规定的时间就是m
        // minPower(powers, rates, m):
        // 如果一定要在time时间内捡完所有衣服，返回最小电量
        // 如果这个最小电量 <= 总电量，说明m时间可行，左侧继续二分答案
        // 如果这个最小电量 > 总电量，说明m时间不可行，右侧继续二分答案
        while (l <= r) {
            m = (l + r) / 2;
            if (minPower(powers, rates, m) <= b) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    public static int minPower(int[] powers, int[] rates, int time) {
        int[] dp = new int[powers.length];
        Arrays.fill(dp, -1);
        return process(powers, rates, 0, time, dp);
    }

    // i....这么多的衣服
    // 在time时间内一定要收完
    // 返回最小电量
    // 如果怎么都收不完，返回系统最大值
    public static int process(int[] powers, int[] rates, int i, int time, int[] dp) {
        int n = powers.length;
        if (i == n) {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        int usedTime = rates[i];
        int nextMinPower = Integer.MAX_VALUE;
        // 这个枚举其实还可以用线段树优化一下
        // 不过对于大思路来说已经无关紧要了
        for (int j = i; j < n && usedTime <= time; j++) {
            // i....j由当前的i号机器负责
            // j+1...由后面机器负责
            nextMinPower = Math.min(nextMinPower, process(powers, rates, j + 1, time, dp));
            usedTime += rates[i];
        }
        int ans = nextMinPower == Integer.MAX_VALUE ? nextMinPower : (powers[i] + nextMinPower);
        dp[i] = ans;
        return ans;
    }

    public static void main(String[] args) {
        int n1 = 3;
        int b1 = 5;
        int[] powers1 = { 1, 2, 3 };
        int[] rates1 = { 7, 5, 3 };

        System.out.println(fast(n1, b1, powers1, rates1));

        int n2 = 3;
        int b2 = 5;
        int[] powers2 = { 6, 2, 3 };
        int[] rates2 = { 7, 5, 3 };

        System.out.println(fast(n2, b2, powers2, rates2));

    }

}
